#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"
#include "algorithm"

using namespace std;

/*
 *给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。



示例 1：

输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 "i" 在 "love" 之前。
示例 2：

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
出现次数依次为 4, 3, 2 和 1 次。
 *
 * */

// 使用优先级队列
vector<string> topKFrequent(vector<string> &words, int k) {

    unordered_map<string, int> res;
    for (const auto &item : words) {
        ++res[item];
    }
    //从小到大排序  top是最小的
    auto cmp = [](const pair<string, int> &a, const pair<string, int> &b) {
        if (a.second == b.second)
            return a.first < b.first; //从大倒小

        return a.second > b.second;//从小到大
    };
    priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> q(cmp);//这边这个初始化很懵逼
    for (const auto &item : res) {
        q.emplace(item);
        if (q.size() > k)
            q.pop();
    }
    vector<string> ret(k);
    for (int i = k - 1; i >= 0; --i) {
        ret[i] = q.top().first;
        q.pop();
    }
    return ret;
}


vector<string> topKFrequent1(vector<string> &words, int k) {

    unordered_map<string, int> res;
    for (const auto &item : words) {
        ++res[item];
    }


    vector<pair<string, int>> res_;
    //从小到大排序  top是最小的
    auto cmp = [](const pair<string, int> &a, const pair<string, int> &b) {
        if (a.second == b.second)
            return a.first > b.first; //从大倒小

        return a.second < b.second;//从小到大
    };
    // https://leetcode.cn/problems/top-k-frequent-words/solutions/785903/qian-kge-gao-pin-dan-ci-by-leetcode-solu-3qk0/
    //这样比较就傻逼了 传入那个mp比较second 就行了
    sort(res_.begin(), res_.end(), cmp);
    res_.resize(k);

    return res_;
}